package edu.ucsd.cse222b.network;

import java.io.BufferedReader;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.jgrapht.GraphPath;
import org.jgrapht.WeightedGraph;
import org.jgrapht.alg.KShortestPaths;
import org.jgrapht.graph.DirectedWeightedSubgraph;
import org.jgrapht.graph.ListenableDirectedWeightedGraph;


import edu.ucsd.cse222b.events.FlowEvent;
import edu.ucsd.cse222b.events.FlowEventQueue;

public final class DCNetwork extends ListenableDirectedWeightedGraph<NetNode, Link> {

	private class ActualRoutingSubnet extends DirectedWeightedSubgraph<NetNode, Link> {
		/**
		 * 
		 */
		private static final long serialVersionUID = 1L;

		public ActualRoutingSubnet(WeightedGraph<NetNode, Link> base,
				Set<NetNode> nodes, Set<Link> links) {
			super(base, nodes, links);
		}

		public List<Link> getLinks() {
			List<Link> links = new ArrayList<Link>();
			for (Link link : edgeSet()) {
				links.add(link);
			}
			return links;
		}

	}

	private DCNetwork(Class<? extends Link> edgeClass) {
		super(edgeClass);
	}

	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;
	
	private static double clock=0.0;
	
	private FlowEventQueue queue=new FlowEventQueue(100);
	
	private DCNetwork originalNetwork=null;
	
	private Set<EndHost> activeSources = new HashSet<EndHost>();

	private Set<NetFlow> transfers = new HashSet<NetFlow>();
	
	private Set<NetFlow> activeTransfers=new HashSet<NetFlow>();
	
	private static double energyConsumptionHost = 0.0;
	
	private static double energyConsumptionRouter = 0.0;
	
	private static double energyConsumptionLink = 0.0;
		
	private static final double upperBound=0.8;
	
	public static DCNetwork getInstance(){
		DCNetwork instance=new DCNetwork(Link.class);
		return instance;
	}
	
	public void buildFatTree(int k){
		int numOfCoreSwitches=k*k/4;
		int numOfPods=k;
		int totalNumOfSwitches=numOfCoreSwitches+numOfPods*k;
		int numOfHosts=k*k*k/4;
		originalNetwork=new DCNetwork(Link.class);
		for(int i=0; i<totalNumOfSwitches; i++){
			originalNetwork.addNetNode(new Router(i));
		}
		
		for(int i=0; i<numOfHosts; i++){
			originalNetwork.addNetNode(new EndHost(i+totalNumOfSwitches));
		}
		for(int i=0; i<numOfCoreSwitches; i++){
			Router coreSwitch=originalNetwork.getRouter(i);
			for(int j=0; j<numOfPods; j++){
				Router aggregationSwitch=originalNetwork.getRouter(numOfCoreSwitches+j*k+i*2/k);
				originalNetwork.installDuplexLink(coreSwitch, 1.0, 5, aggregationSwitch, 1.0, 5);
			}
		}
		for(int i=0; i<numOfPods; i++){
			for(int m=0; m<k/2; m++)
			{
				Router aggregationSwitch=originalNetwork.getRouter(numOfCoreSwitches+i*k+m);
				for(int n=k/2; n<k; n++)
				{
					Router edgeSwitch=originalNetwork.getRouter(numOfCoreSwitches+i*k+n);
					originalNetwork.installDuplexLink(aggregationSwitch, 1.0, 0.5, edgeSwitch, 1.0, 0.5);
				}
			}
		}
		for(int i=0; i<numOfPods; i++){
			for(int n=k/2; n<k; n++)
			{
				Router edgeSwitch=originalNetwork.getRouter(numOfCoreSwitches+i*k+n);
				for(int m=0; m<k/2; m++)
				{
					EndHost host=originalNetwork.getEndHost(totalNumOfSwitches+i*k+(n-k/2)*k/2+ m);
					originalNetwork.installDuplexLink(edgeSwitch, 1.0, 0.5, host, 1.0, 0.5);
				}
			}
		}
	}
	
	private void restoreToOriginalNetwork(){
		//first restore to empty graph
		Set<NetNode> nodes=new HashSet<NetNode>();
		nodes.addAll(getNetNodes());
		removeAllVertices(nodes);
		
		//then restore to original network topology WITHOUT flow information
		for(NetNode node : originalNetwork.getNetNodes()){
			if(node instanceof Router){
				addNetNode(new Router(node.getId()));
			}else if(node instanceof EndHost){
				addNetNode(new EndHost(node.getId()));
			}
		}
		for(Link link : originalNetwork.getLinks()){
			NetNode src=getNetNode(link.getSrcNode().getId());
			NetNode dst=getNetNode(link.getDstNode().getId());
			installDuplexLink(src, link.getCost(), link.getBandwidth(), dst, link.getCost(), link.getBandwidth());
		}
	}
	
	public void createFlows(BufferedReader reader){
		try {
			//we will group flow arrival events with same arrival time together
			Map<Double, ArrayList<NetFlow>> temp=new HashMap<Double, ArrayList<NetFlow>>();
			String line;
			while((line=reader.readLine())!=null){
				String [] flowSpec=line.split(" ");
				EndHost src=new EndHost(Long.parseLong(flowSpec[0]));
				EndHost dst=new EndHost(Long.parseLong(flowSpec[1]));
				double size=Double.parseDouble(flowSpec[2]);
				double startTime=Double.parseDouble(flowSpec[3]);
				double endTime=Double.parseDouble(flowSpec[4]);
				NetFlow flow=new NetFlow(src, dst, size, startTime, endTime);
				transfers.add(flow);
				if(temp.containsKey(startTime)){
					temp.get(startTime).add(flow);
				}else{
					temp.put(startTime, new ArrayList<NetFlow>());
					temp.get(startTime).add(flow);
				}
			}
			//we have grouped all the arrival events, so we enqueue them all
			for(Double startTime : temp.keySet()){
				FlowEvent event=new FlowEvent(startTime);
				for(NetFlow flow : temp.get(startTime)){
					event.addFlowArriving(flow);
				}
				queue.enqueEvent(event);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	private void prepareFlows(){
		activeSources.clear();
		for(NetFlow flow : activeTransfers){
			EndHost src=getEndHost(flow.getSource().getId());
			EndHost dst=getEndHost(flow.getDestination().getId());
			flow.setSource(src);
			flow.setDestination(dst);
			src.addFlow(flow);
			activeSources.add(src);
		}
	}
	


	private void getEqualCostRoutingPathList(EndHost src) {
		KShortestPaths<NetNode, Link> shortestPaths = new KShortestPaths<NetNode, Link>(this, src, transfers.size());
		for (NetFlow flow : src.getFlows()) {
			EndHost dst = flow.getDestination();
			List<GraphPath<NetNode, Link>> paths = shortestPaths.getPaths(dst);

			for (GraphPath<NetNode, Link> path : paths) {
				if (path.getWeight() == paths.get(0).getWeight()) {
					src.addOutgoingPath(dst, new RoutingPath(this, src, dst, path.getEdgeList(), path.getWeight()));
				}
			}
		}
	}

	public void computeRoutingPaths() {
		for(EndHost src : activeSources){
			getEqualCostRoutingPathList(src);
			src.scheduleFlows();
		}
	}

	public void allocBandwidth() {
		Set<NetNode> nodes = new HashSet<NetNode>();
		Set<Link> links = new HashSet<Link>();
		
		for (NetFlow flow : activeTransfers) {
			/*reset each active flow such that they are using 0 bandwidth, we do this before each time
			* we allocate bandwidth
			*/
			flow.setSaturated(false);
			flow.setCurrentBandwidth(0);
			flow.setAvailableBandwidth(0);
			for (Link link : flow.getLinks()) {
				links.add(link);
				nodes.add(link.getSrcNode());
				nodes.add(link.getDstNode());
			}
		}
		ActualRoutingSubnet subnet = new ActualRoutingSubnet(this, nodes, links);

		int numOfUnsaturatedFlows = activeTransfers.size();

		while (numOfUnsaturatedFlows > 0) {
			/* find bottleneck link (link which should be saturated next) */
			double minIncreaseRate = 10000.0;
			
			for (Link link : subnet.getLinks()) {
				if (link.getAvailableBandwidth()>0 && minIncreaseRate * link.getNumOfUnsaturatedFlows() > link.getAvailableBandwidth()) {
					minIncreaseRate = link.getAvailableBandwidth() / link.getNumOfUnsaturatedFlows();
				}
			}
			
			/*
			 * increase all flows at the same rate until some of them saturate
			 */
			for (NetFlow flow : activeTransfers) {
				if (flow.isSaturated() == false) {
					flow.increaseAvailableBandwidth(minIncreaseRate);
					for (Link link : flow.getLinks()) {
						link.allocBandwidth(minIncreaseRate);
						if(link.getAvailableBandwidth()<=0){
							flow.setSaturated(true);
						}
					}
					if(flow.isSaturated()){
						numOfUnsaturatedFlows--;
					}
				}
			}
		}
	}
	
	private void acceptBandwidth() {
		for(NetFlow flow : activeTransfers){
			flow.acceptBandwidth();
		}
		printBandwidthAllocation();
	}
	
	private boolean checkBandwidthUtilization(){
		//find overloaded link
		for(Link link : getLinks()){
			if(link.getUtilizedBandwidth()>=upperBound*link.getBandwidth()){
				return false;
			}
		}
		return true;
	}
	
	private void phaseOneSelectPaths(){
		//TODO implement paths selection algorithm, you may change the signature of this method
		//need to pass some hint so that can do path selection based on the heuristics
		//default: return the whole graph
		
	
		Set<NetNode> nodes = this.getNetNodes();
		Set<Link> links = this.getLinks();
		
		Set<NetNode> newNodes = new HashSet<NetNode>();
		Set<Link> newLinks = new HashSet<Link>();
		
		//for each active sources find paths and add them to the graph instance
		for(EndHost src : activeSources)
		{
			KShortestPaths<NetNode, Link> shortestPaths = new KShortestPaths<NetNode, Link>(this, src, this.getLinks().size());
			for (NetFlow flow : src.getFlows()) 
			{
				EndHost dst = flow.getDestination();
				List<GraphPath<NetNode, Link>> paths = shortestPaths.getPaths(dst);
				
				CandidatePath minCapacityPath = new CandidatePath(this, src, dst, Collections.EMPTY_LIST, 0);
								
				for (GraphPath<NetNode, Link> path : paths) 
				{
					if (calculatePathCapacity(path)< calculatePathCapacity(minCapacityPath))
					{
						if(Collections.disjoint(path.getEdgeList(),minCapacityPath.getEdgeList()))
						{
							minCapacityPath = new CandidatePath(this, src, dst, path.getEdgeList(), path.getWeight());							
						}
					}
				}
				newNodes.addAll(minCapacityPath.getNodes());
				newLinks.addAll(minCapacityPath.getLinks());
			}
		}

		Set<NetNode> tmpNodes = new HashSet<NetNode>();
		Set<Link> tmpLinks = new HashSet<Link>();
		
		tmpNodes.addAll(nodes);
		tmpLinks.addAll(links);
		
		tmpNodes.removeAll(newNodes);
		tmpLinks.removeAll(newLinks);
		
		this.removeAllVertices(tmpNodes);
		this.removeAllEdges(tmpLinks);
		
	}
	
	private double calculatePathCapacity(GraphPath<NetNode, Link> path) 
	{
		double capacity = Double.MAX_VALUE;
		if (path.getEdgeList().isEmpty())
			return capacity;
		for(Link link : path.getEdgeList())
		{
			if(capacity > link.getAvailableBandwidth())
				capacity = link.getAvailableBandwidth();
		}
		return capacity;
	}
	

	
	private void handleFlowEvent(FlowEvent event){
		
		Set<NetNode> activeRouters = new HashSet<NetNode>(); 
		Set<NetNode> activeHosts = new HashSet<NetNode>(); 
		Set<Link> activeLinks = new HashSet<Link>(); 
		
		double transferTime = event.getTimestamp()-clock;
		for(NetFlow flow : activeTransfers){
			flow.doTransfer(event.getTimestamp()-clock);
			if(flow.getRemainingSize()<=0){
				event.getFlowsFinishing().add(flow);
			}
			
			// code for energy consumption
			activeRouters.addAll(flow.getRouters());
			
			activeHosts.add(flow.getSource());
			activeHosts.add(flow.getDestination());
			
			activeLinks.addAll(flow.getLinks());
			
		}
		energyConsumptionRouter += activeRouters.size() * transferTime;
		energyConsumptionHost += activeHosts.size() * transferTime;
		energyConsumptionLink += activeLinks.size() * transferTime;
		
		clock=event.getTimestamp();
		activeTransfers.removeAll(event.getFlowsFinishing());
		activeTransfers.addAll(event.getFlowsArriving());
		
		if(activeTransfers.size()==0){
			return;
		}
		
		int maxRetries=3, numOfAttempts=0;
		boolean success=false;
		
		numOfAttempts=0;
		success=false;
		
		while(numOfAttempts < maxRetries){
			restoreToOriginalNetwork();
			prepareFlows();
			phaseOneSelectPaths();
			computeRoutingPaths();
			allocBandwidth();
			acceptBandwidth();
			
			success=checkBandwidthUtilization();
			if(success){
				break;
			}
			numOfAttempts++;
		}
		if(!success){
			System.out.println("Cannot sustain flows");
			return;
		}
		double nextEpoch=100000.0;
		//at this time, there must already be a legal flow schedule and bandwidth allocation
		for(NetFlow flow : activeTransfers){
			if(nextEpoch*flow.getCurrentBandwidth()>flow.getRemainingSize()){
				nextEpoch=flow.getRemainingSize()/flow.getCurrentBandwidth();
			}
		}
		Set<NetFlow> temp=new HashSet<NetFlow>();
		for(NetFlow flow : activeTransfers){
			if(flow.getRemainingSize()<=nextEpoch*flow.getCurrentBandwidth()){
				temp.add(flow);
			}
		}
		
		FlowEvent event1=queue.peekEvent();
		if(event1==null){
			FlowEvent nextEvent=new FlowEvent(clock+nextEpoch);
			nextEvent.getFlowsFinishing().addAll(temp);
			queue.enqueEvent(nextEvent);
		}else{
			if(event1.getTimestamp()>clock+nextEpoch){
				FlowEvent nextEvent=new FlowEvent(clock+nextEpoch);
				nextEvent.getFlowsFinishing().addAll(temp);
				queue.enqueEvent(nextEvent);
			}else if(event1.getTimestamp()==clock+nextEpoch){
				event1.getFlowsFinishing().addAll(temp);
			}
		}
	}
	
	public void execute(){
		while(queue.getEvents().size()>0){
			FlowEvent event=queue.dequeueEvent();
			handleFlowEvent(event);
		}
	}
	
	
	public double getEnergyConsumption()
	{
		return energyConsumptionRouter + energyConsumptionHost + 0.1*energyConsumptionLink;
	}
	
	public Set<NetNode> getNetNodes() {
		return vertexSet();
	}

	public Set<EndHost> getEndHosts() {
		HashSet<EndHost> endHosts = new HashSet<EndHost>();
		for (NetNode node : getNetNodes()) {
			if (node instanceof EndHost) {
				endHosts.add((EndHost) node);
			}
		}
		return endHosts;
	}
	
	public EndHost getEndHost(long id){
		for(NetNode node : getNetNodes()){
			if(node instanceof EndHost && id==node.getId()){
				return (EndHost)node;
			}
		}
		return null;
	}
	
	public Router getRouter(long id){
		for(NetNode node : getNetNodes()){
			if(node instanceof Router && id==node.getId()){
				return (Router) node;
			}
		}
		return null;
	}
	
	public NetNode getNetNode(long id){
		for(NetNode node : getNetNodes()){
			if(node.getId()==id){
				return node;
			}
		}
		return null;
	}

	public Set<Router> getRouters() {
		HashSet<Router> routers = new HashSet<Router>();
		for (NetNode node : getNetNodes()) {
			if (node instanceof Router) {
				routers.add((Router) node);
			}
		}
		return routers;
	}

	public Set<Link> getLinks() {
		return edgeSet();
	}

	public Link getLink(NetNode src, NetNode dst) {
		return getEdge(src, dst);
	}
	
	public void setTransfers(Set<NetFlow> transfers) {
		this.transfers = transfers;
	}

	public Set<NetFlow> getTransfers() {
		return transfers;
	}
	
	public void addNetNode(NetNode node) {
		addVertex(node);
	}

	public void addLink(NetNode src, NetNode dst) {
		addEdge(src, dst);
	}
	
	public void installDuplexLink(NetNode node1, double cost1,
		double bandwidth1, NetNode node2, double cost2, double bandwidth2) {
		addLink(node1, node2);
		addLink(node2, node1);
		setEdgeWeight(getLink(node1, node2), cost1);
		setEdgeWeight(getLink(node2, node1), cost2);
		getLink(node1, node2).setBandwidth(bandwidth1);
		getLink(node2, node1).setBandwidth(bandwidth2);
	}
	
	private void printBandwidthAllocation(){
		System.out.println("++++++++++++++++++++++++++++++++++++++++++++++++++++++++");
		for(NetFlow flow : activeTransfers){
			System.out.println(flow);
		}
		System.out.println("++++++++++++++++++++++++++++++++++++++++++++++++++++++++");
	}
}